package algorithm;

public class MergeSort {
	public static void mergeSort(int[] a) {
		mergeSort(a, 0, a.length - 1);
	}

	public static void mergeSort(int[] a, int p, int r) {
		if (r > p) {
			int m = (p + r) / 2;
			mergeSort(a, p, m);
			mergeSort(a, m + 1, r);
			merge(a, p, m, r);
		}
	}

	public static void merge(int[] a, int p, int q, int r) {
		int[] b = new int[q - p + 1];
		int[] c = new int[r - q];
		for (int i = p; i <= r; i++) {
			if (i <= q) {
				b[i - p] = a[i];
			} else {
				c[i - q - 1] = a[i];
			}
		}
		int b_i = 0;
		int c_i = 0;
		for (int j = p; j <= r; j++) {
			if (b_i == b.length && c_i == c.length) {
				System.out.print("error");
			} else if (b_i == b.length) {
				a[j] = c[c_i];
				c_i++;
			} else if (c_i == c.length) {
				a[j] = b[b_i];
				b_i++;
			} else if (b[b_i] <= c[c_i]) {
				a[j] = b[b_i];
				b_i++;
			} else {
				a[j] = c[c_i];
				c_i++;
			}
		}
	}
}
